package Simple2;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

public class Array_Hoppers_Chanllenge {

	int[] array;
	String out;
	public Array_Hoppers_Chanllenge(String args){
		this.array = readFile(args);
//		this.out = minHop(array);
		this.out = minHop2(array);
	}
	
	/**
	 * Find the minHop to print out.
	 * @param input
	 * @return
	 */
	public String minHop(int[] input){
		int len = input.length;
		int[] hoppers = new int[len];
		String to_return = "";
		if(len==0 || input[0]==0)
			to_return = "failure";
		else{
			hoppers[0] = 0;
			for(int i = 1; i <len; i++){
				hoppers[i] = Integer.MAX_VALUE;
				for(int j =0; j< i; j++){
					if(i<=j+input[j] && hoppers[j] != Integer.MAX_VALUE){
						hoppers[i] = hoppers[j]+1;
						break;
					}
				}
			}
		}
		//Change the steps to the output string
		if(hoppers[len-1] == Integer.MAX_VALUE || hoppers[len-1] == 0)
			to_return = "failure";
		else{
			to_return = String.valueOf(len-1) + ", out";
			int flag = hoppers[len-1];
			for(int i=len-1;i>=0;i--){
				int temp = hoppers[i];
				if(temp!=flag){
					to_return = String.valueOf(i) + ", " + to_return;
					flag = temp;
				}
			}
		}	
		return to_return;
			
	}
	
	public String minHop2(int[] input){
		ArrayList<Integer> ret = new ArrayList<Integer>();
		ArrayList<Integer> temp = new ArrayList<Integer>();
		int pre=0,cur=0; 
		for(int i=0;i<input.length;++i){
			if(i>cur) break; //if i is larger than the biggest hop, break;
			if(i>pre){
				pre=cur;
				ret.add(temp.get(temp.size()-1));
			}
			if(input[i]+i>cur){
				cur=input[i]+i;
				temp.add(i);
			}
		}
		if(temp.get(temp.size()-1)==input.length-1)
			ret.add(input.length-1);
		String to_return = "";
		if(cur<input.length){
			to_return="failure";
			return to_return;
		}
		for(int i=0;i<ret.size();++i){
			to_return += ret.get(i)+", ";
		}
		to_return +="out";
		return to_return;
	}
	
	
	/**
	 * Get the input data from the file,
	 * The data form is 3
	 * 					4
	 * 					5
	 * 					6
	 * which will return [3,4,5,6]
	 * @param args		the file name
	 * @return 			an integer array	
	 */
	public int[] readFile(String args) {
		//Get the input File line by line
		int[] to_return = null;
		try {
			FileReader fin = new FileReader(args);
			BufferedReader in = new BufferedReader(fin);
			String line;
			ArrayList<Integer> array = new ArrayList<Integer>();
			while((line=in.readLine()) != null){
				try{
					array.add(Integer.valueOf(line));		
				}
				catch(NumberFormatException e){
					System.err.println("Error Input");
				}
				
			}					
			to_return = new int[array.size()];
			for(int i=0;i<array.size();i++){
				to_return[i] = array.get(i);
			}
			in.close();
			fin.close();
			
		} catch (FileNotFoundException e) {
			System.err.println("Cannot find the file.");
			e.printStackTrace();
		}
		catch (IOException e){
			System.err.println("IO exception");
			e.printStackTrace();
		}
		return to_return;	
	}
	
	public static void main(String[] args) {
		Array_Hoppers_Chanllenge test = 
				new Array_Hoppers_Chanllenge("src/Simple2/1.txt");
		int[] temp = test.array;
		for(int i=0;i<temp.length;i++){
			System.out.print(temp[i]+", ");
		}
		System.out.println("\n"+test.out);
		
	}

}
